package nz.ac.massey.cs.domain;

import java.util.ArrayList;

import nz.ac.massey.cs.utils.CellType;

// this class implements solver which can take in a sudoku object and solve it
public class Solver implements ISolver{
	
		private ISudoku sudoku;
		int x = 0;
		int y = 0;
		private ArrayList<Cell> criticalCellList;
		private Boolean isFirstRun = true;
		
		public Solver() {
			this.criticalCellList = new ArrayList<Cell>();
		}
		
		public Solver(ISudoku sudoku) {
			this.sudoku = sudoku;
			this.criticalCellList = new ArrayList<Cell>();
		} 
		
		
		public void setSudoku(ISudoku sudoku) {
			this.sudoku = sudoku;
		}
		
		public ISudoku getSudoku() {
			return sudoku;
		} 
		
//		public boolean solve(int rowIdx, int colIdx) {
//
//			if ( colIdx == sudoku.getColSize() ) {
//				colIdx = 0; 
//				rowIdx++; 
//				
//				// if rowIdx  == sudoku.getRowSize then get solution
//				if ( rowIdx == sudoku.getRowSize() ) {
//			    	return true; 
//			    }
//				
//			}
//			
//			//System.out.println("row:"+ rowIdx +" column:" +colIdx);
//			Cell cell = this.sudoku.getCellByIndex(rowIdx, colIdx);
//			
//			//System.out.println("Get cell from Sudoku instance: "+ cell.toString());
//			
//			// skip filled cells
//			if ( cell.getType() == CellType.VARIABLE 
//					&& cell.getValue().equals("0")) {
//				return solve(rowIdx, colIdx+1);
//			}
//			
//			//System.out.println("try to solve cell: "+ cell.toString());
//			//!!! need to change using Range
//			for (int value = 1; value <= 9; value++) {
//				//System.out.println("try potential value: "+ value);
//				ArrayList<IConstraint> constraintList = cell.getConstraints();
//				
//				boolean isValueViolated = false;
//				for (IConstraint con:constraintList ) {
//					
//					if ( con.isViolated() ) {
//						isValueViolated = true;
//						break;
//						
//					}
//					else {
//						continue;
//					}
//				}
//				
//				if ( false == isValueViolated ) {
//					if ( solve(rowIdx, colIdx+1) ) {
//						return true;
//					}
//				}
//				else {
//					continue;
//				}
//			}
//			
//			// reset on backtrack
//			cell.setValue("0");  
//			return false;
//		}
//		
		/*
		 * for back tracking
		 */
		private Cell processNode(int x, int y)
		{
			Cell cellToReduce = sudoku.getCellByIndex(y, x);
			if(cellToReduce.getType().equals(CellType.VARIABLE))
			{
				Boolean viable = true;
				Boolean upto = false;
				Boolean done = false ;
				for(int i =0; i < cellToReduce.getPossibleValueList().size() ; i++)
				{
					String value = cellToReduce.getPossibleValueList().get(i);
					if(done)
					{
						if(upto)
						{
							cellToReduce.setValue(value);
							for(IConstraint con:cellToReduce.getConstraints())
							{
								if(!con.isViolated() && viable)
								{
									viable = true;
								}
								else
								{
									viable = false;
								}
							}
							if(viable)
							{
								this.x = x;
								this.y = y;
								System.out.print(x+ "  " + y);
								return cellToReduce;
							}
							viable = true;
						}
					}
					else
					{
						if(value != cellToReduce.getValue() && !upto )
						{
							continue;
						}
						else
						{
							upto = true;
							done = true;
							value = cellToReduce.getPossibleValueList().get(i);
						}
					}
				}
				cellToReduce.setValue("");
			}
			
			x--;
			if(y < 0 && x < 0)
			{
				return null; // not solvable
			}
			else if(x < 0)
			{
				x = sudoku.getRowSize() - 1;
				y--;
			}
			
			return processNode(x, y); 
		}
		
		public Cell solveNext() {
			if(sudoku.puzzleComplete())
			{
				System.out.println("We Win");
			}
			
			// first time solve Sudoku, initialize possible values of cell 
			if ( true == isFirstRun ) {
				System.out.println("first time run");
				updatePossibleValuesForCell();
				findCriticalCell();
			}
			
			if ( this.criticalCellList.size() > 0 ){
				for ( Cell criticalCell:this.criticalCellList ){
					criticalCell.setValue(criticalCell.getPossibleValueList().get(0));
					criticalCell.setType(CellType.FIXED);
					System.out.println("filled "+criticalCell.toString()+"cell type:"+criticalCell.getType());
					this.criticalCellList.remove(criticalCell);
					updatePossibleValuesForCell();
					findCriticalCell();
					return criticalCell;
				}
			}
			else {
				isFirstRun = false;
			}
		
		    Cell cellToReduce = sudoku.getCellByIndex(y, x);
		   
			while(cellToReduce.getValue() != "" || cellToReduce.getType() != CellType.VARIABLE)
			{
				
				x++;
				if(y >= sudoku.getColSize() -1 && x >= sudoku.getRowSize())
				{
					System.out.println("we win");
					return null;
//					y = 0;
//					x=0;
				}
				else
				{
					if(x >= sudoku.getRowSize())
					{
						y++;
						x = 0;
					}
				}
				cellToReduce = sudoku.getCellByIndex(y, x);
			}
			
			Boolean hasValue = false;
			Boolean viable = true;
			for(String value:cellToReduce.getPossibleValueList())
			{
				
					cellToReduce.setValue(value);
					for(IConstraint con:cellToReduce.getConstraints())
					{
						if(!con.isViolated() && viable)
						{
							viable = true;
						}
						else
						{
							viable = false;
						}
					}
					if(viable)
					{
						return cellToReduce;
					}
					viable = true;
				}
			cellToReduce.setValue("");
			try{
			do
			{
				x--;
				if(y < 0 && x < 0)
				{
					return null; // not solvable
				}
				else if(x < 0)
				{
					x = sudoku.getRowSize() - 1;
					y--;
				}
			}while(sudoku.getCellByIndex(y, x).getType() != CellType.VARIABLE); // threw an exception after changing puzzles
			} catch (Exception e) { System.out.println("X =" + x +" Y =" + y);}
			return processNode(x, y);
			
//			cellToReduce = sudoku.getCellByIndex(y, x);
//			int i=0;
//			while(cellToReduce.getPossibleValueList().get(i) != cellToReduce.getValue())
//			{
//				i++;
//			}
//			
//			for(String value:cellToReduce.getPossibleValueList())
//			{
//				
//					cellToReduce.setValue(value);
//					for(IConstraint con:cellToReduce.getConstraints())
//					{
//						if(!con.isViolated() && viable)
//						{
//							viable = true;
//						}
//						else
//						{
//							viable = false;
//						}
//					}
//					if(viable)
//					{
//						return cellToReduce;
//					}
//					viable = true;
//				}
			
//			if(cellToReduce.getValue() != "")
//			{
//				solveNext();
//			}
//			for(int i =0;i < cells.length;i++)
//			{
//				for(int j = 0;j< cells[1].length;j++ )
//				{
//					if(cells[i][j].getValue().equals(""))
//					{
//						cellToReduce = cells[i][j];
//						break;
//					}
//				}
//			}
//			ArrayList<String> stuffToRemove = new ArrayList<String>();
//			
//			for(String value:cellToReduce.getPossibleValueList())
//			{
//				cellToReduce.setValue(value);
//				for(IConstraint con:cellToReduce.getConstraints())
//				{
//					if(con.isViolated())
//					{
//						System.out.println(cellToReduce.getValue());
//						stuffToRemove.add(cellToReduce.getValue());
//					}
//				}				
//			}
//			//ArrayList<String> stuffToRemove = new ArrayList<String>();
//			
//			for(String value:cellToReduce.getPossibleValueList())
//			{
//				cellToReduce.setValue(value);
//				if(isNotPossibleElseWhere(cellToReduce))
//				{
//					for(String obsoultevalue:cellToReduce.getPossibleValueList())
//					{
//						if(obsoultevalue != value)
//						{
//							stuffToRemove.add(obsoultevalue);
//						}
//					}
//				}
//			}
//			
//			for(String value:stuffToRemove)
//			{
//				cellToReduce.removePossibleValue(value);
//			}
//
//			System.out.print(cellToReduce.getPossibleValueList() + "\n");
//			if(cellToReduce.getPossibleValueList().size() == 1)
//			{
//				cellToReduce.setValue(cellToReduce.getPossibleValueList().get(0));
//				//System.out.print(cellToReduce.getPossibleValueList() + "\n");
//			}
//			else
//			{
//				cellToReduce.setValue("");
//			}
//			return cellToReduce;
		}
		
		private void updatePossibleValuesForCell(){
			Cell[][] cellMatrix = this.sudoku.getCells();
			for (int i=0; i<this.sudoku.getRowSize(); i++) {
				for (int j=0; j<this.sudoku.getColSize(); j++){
					
					if ( CellType.VARIABLE != cellMatrix[i][j].getType() 
							|| cellMatrix[i][j].getType() == CellType.FIXED) {
						continue;
					}
					ArrayList<String> obsoleteValueList = new ArrayList<String>();
					for(String value:cellMatrix[i][j].getPossibleValueList())
					{
						cellMatrix[i][j].setValue(value);
						for(IConstraint con:cellMatrix[i][j].getConstraints())
						{
							if(con.isViolated())
							{
								obsoleteValueList.add(cellMatrix[i][j].getValue());
							}
						}				
					}
					//ArrayList<String> stuffToRemove = new ArrayList<String>();
					
					for(String value:cellMatrix[i][j].getPossibleValueList())
					{
						cellMatrix[i][j].setValue(value);
						if(isNotPossibleElseWhere(cellMatrix[i][j]))
						{
							for(String obsoultevalue:cellMatrix[i][j].getPossibleValueList())
							{
								if(obsoultevalue != value)
								{
									obsoleteValueList.add(obsoultevalue);
								}
							}
						}
					}
					
					for(String value:obsoleteValueList)
					{
						cellMatrix[i][j].removePossibleValue(value);
					}
				
					cellMatrix[i][j].setValue("");
//					System.out.println(cellMatrix[i][j].toString()+"get possible values:"+cellMatrix[i][j].getPossibleValueList());
				}
			}
//			System.out.println("finish initPossibleValuesForCell");
		}
		
		public boolean isCellInCriticalList(Cell tempCell) {
			if ( 0 == this.criticalCellList.size() ){
				return false;
			}
			for (Cell criticalCell:this.criticalCellList ){
				if (tempCell.getRowIdx() == criticalCell.getRowIdx() 
						&& tempCell.getColIdx() == criticalCell.getColIdx() ) {
					return true;
				}
			}
			return true;
		}
		
		public void findCriticalCell() {
			Cell[][] cellMatrix = this.sudoku.getCells();
			for (int i=0; i<this.sudoku.getRowSize(); i++){
				for (int j=0; j<this.sudoku.getColSize(); j++) {
					if ( cellMatrix[i][j].getType() == CellType.VARIABLE ) {
						if ( 1 == cellMatrix[i][j].getPossibleValueList().size() ){
							if (isCellInCriticalList(cellMatrix[i][j])) {
								continue;
							}
							this.criticalCellList.add(cellMatrix[i][j]);
//							System.out.println("get a cell with unique value"+cellMatrix[i][j].toString());
						}
					}
				}
			}
		}
		
		
		private boolean isNotPossibleElseWhere(Cell cell)
		{
			for(IConstraint con:cell.getConstraints())
			{
				if(isNotPossibleInConstraint(cell, con))
				{
					return true;
				}
			}
			return false;
		}
		
		private boolean isNotPossibleInConstraint(Cell cell,IConstraint con)
		{
			for(Cell test:con.getCells())
			{
				if(test.getPossibleValueList().contains(cell.getValue()))
				{
					return false;
				}
			}
			return true;
		}
		
		// add logic for when a group of cells have the same range and 
}
